package t2

type MapSum struct {
	cnt  map[string]int
	root *Trie
}

type Trie struct {
	children [26]*Trie
	val      int
}

func Constructor() MapSum {
	return MapSum{map[string]int{}, &Trie{}}
}

func (this *MapSum) Insert(key string, val int) {
	node := this.root
	delta := val
	if this.cnt[key] > 0 {
		delta -= this.cnt[key]
	}
	this.cnt[key] = val
	for _, c := range key {
		idx := c - 'a'
		if node.children[idx] == nil {
			node.children[idx] = &Trie{}
		}
		node.children[idx].val += delta
		node = node.children[idx]
	}
}

func (this *MapSum) Sum(prefix string) int {
	node := this.root
	for _, c := range prefix {
		idx := c - 'a'
		if node.children[idx] == nil {
			return 0
		}
		node = node.children[idx]
	}
	return node.val
}
